πŸ“‚ Trie(트라이)

@Seongukbaek Posted May 25, 2022 Β· Updated May 25, 2022 Β· 15 min read

🧷 트라이

효율적인 λ¬Έμžμ—΄ μ €μž₯ 및 탐색이 κ°€λŠ₯ν•œ μžλ£Œκ΅¬μ‘°μ΄λ‹€.

μ›λž˜λŠ” Tri 둜 λΆˆλ Έμ—ˆλ‹€. ν•˜μ§€λ§Œ 말둜 ν•  λ•Œ Tree 와 κ΅¬λΆ„λ˜μ§€ μ•ŠλŠ” κ²½ν–₯이 μžˆμ–΄ Trie(트라이) 둜 뢈리기 μ‹œμž‘ν–ˆλ‹€.

수 λ§Žμ€ λ¬Έμžμ—΄μ„ μ €μž₯ν•˜μ˜€λŠ”λ° μž…λ ₯으둜 μ–΄λ–€ λ¬Έμžμ—΄μ΄ μ£Όμ–΄μ‘Œμ„ λ•Œ, λ‚΄κ°€ μ €μž₯ν•œ λ¬Έμžμ—΄μ— ν¬ν•¨λœ λ¬Έμžμ—΄μΈμ§€ μ•Œ 수 μžˆλŠ” 방법은 μ•„λž˜μ™€ 같은 방식듀이 μžˆμ„ 것이닀.

  1. λ‹¨μˆœ 비ꡐ

    • λ‹¨μˆœν•˜κ²Œ 전체 λ¬Έμžμ—΄μ˜ μ²˜μŒλΆ€ν„° λκΉŒμ§€ κ°œλ³„ 문자λ₯Ό λΉ„κ΅ν•˜λŠ” 방식
    • μ΅œλŒ€ λ¬Έμžμ—΄ 길이 m, 전체 문자 개수 n 개일 경우, μ‹œκ°„λ³΅μž‘λ„: O(nm)O(nm)
  2. 이진 탐색 기법

    • 전체 λ¬Έμžμ—΄μ„ 사전 순으둜 λ°°μ—΄ μ €μž₯ ν›„, 쀑간 κ°’κ³Ό 비ꡐ해 μ‚¬μ „μ μœΌλ‘œ 이전이면 쒌츑의 반 / 이후면 우츑의 반으둜 비ꡐ 반볡 방식
    • μ΅œλŒ€ λ¬Έμžμ—΄ 길이 m, 전체 문자 개수 n 개일 경우, μ‹œκ°„λ³΅μž‘λ„: μ •λ ¬: O(nmlogn)O(nmlogn) / 탐색: O(mlogn)O(mlogn) 즉, O(nmlogn)O(nmlogn)
  3. 트라이(Trie)

    • K-μ§„ 트리 ꡬ쑰λ₯Ό 톡해 λ¬Έμžμ—΄μ„ μ €μž₯ν•˜λŠ” 방식
    • game μ΄λΌλŠ” 단어λ₯Ό μ°ΎλŠ”λ‹€λ©΄, g λ₯Ό μ°Ύκ³  μˆœμ„œλŒ€λ‘œ a, m, e λ₯Ό μ°ΎλŠ”λ°, 이λ₯Ό νŠΈλ¦¬ν˜•μ‹μœΌλ‘œ κ΅¬ν˜„ν•œ 것
    • 맨 μ•žμ˜ 접두어(prefix)λΆ€ν„° μ‹œμž‘ν•˜μ—¬ 단어 전체λ₯Ό μ°Ύμ•„κ°€λŠ” κ³Όμ •μ΄λ―€λ‘œ 접두사 트리(Prefix-Tree)라고도 ν•œλ‹€.
    • λ¬Έμžμ—΄ μ €μž₯을 μœ„ν•œ 곡간을 많이 μ“°μ§€λ§Œ 탐색에 맀우 νš¨μœ¨μ μ΄λΌλŠ” νŠΉμ„±μ„ κ°–λŠ”λ‹€.
    • μ΅œλŒ€ λ¬Έμžμ—΄ 길이 m 일 λ•Œ 문자의 κ°œμˆ˜μ™€ λ¬΄κ΄€ν•˜κ²Œ μ‹œκ°„λ³΅μž‘λ„: O(m)O(m)

      • λ¬Έμžμ—΄ 길이가 λ„ˆλ¬΄ μ»€μ„œ Map 등을 μ΄μš©ν•΄ 동적 할당을 ν•΄μ•Ό ν•˜λŠ” 경우 O(mlogn)O(mlogn)만큼 μ†Œμš”ν•  수 μžˆλ‹€.
{"bar", "bag", "bark", "dog", "do", "door"}

πŸͺš μž₯단점

νŠΈλΌμ΄λŠ” ν•΄μ‹œ ν…Œμ΄λΈ”μ„ λŒ€μ²΄ν•˜λŠ” 데 μ‚¬μš©λ  수 μžˆλ‹€.

μž₯점

  • λΆˆμ™„μ „ν•œ ν•΄μ‹œ ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•˜λŠ” ν•΄μ‹œν…Œμ΄λΈ”κ³Ό 비ꡐ할 λ•Œ, μžλ£Œμ— μ ‘κ·Όν•  λ•Œ μ΅œμ•…μ˜ 경우 더 μœ λ¦¬ν•œ μ‹œκ°„λ³΅μž‘λ„λ₯Ό κ°–λŠ”λ‹€.

    • m이 탐색할 λ¬Έμžμ—΄μ˜ 길이일 λ•Œ μ‹œκ°„λ³΅μž‘λ„λŠ” O(m)O(m)이닀.
    • 보톡 ν•΄μ‹œν…Œμ΄λΈ”μ€ 탐색 μ‹œκ°„μ΄ O(1)O(1)이고 ν•΄μ‹œ ν•¨μˆ˜ 평가 μ‹œκ°„μ΄ O(m)O(m)μ΄μ§€λ§Œ, λΆˆμ™„μ „ν•œ ν•΄μ‹œ ν…Œμ΄λΈ”μ€ ν‚€ 좩돌이 일어날 수 μžˆμœΌλ―€λ‘œ, O(N)O(N)이 될 수 μžˆλ‹€.
  • νŠΈλΌμ΄μ—μ„œλŠ” ν‚€ 좩돌이 μΌμ–΄λ‚˜μ§€ μ•ŠλŠ”λ‹€.
  • μ—¬λŸ¬ 값이 ν•˜λ‚˜μ˜ 킀와 μ—°κ΄€λ˜μ–΄ μžˆμ§€ μ•ŠλŠ” ν•œ 버킷이 ν•„μš” μ—†λ‹€.
  • ν•΄μ‹œ ν•¨μˆ˜κ°€ 없어도 λœλ‹€. ν‚€κ°€ λŠ˜μ–΄λ‚  λ•Œ ν•΄μ‹œ ν•¨μˆ˜λ₯Ό λ³€κ²½ν•  ν•„μš”λ„ μ—†λ‹€.
  • λͺ¨λ“  ν•­λͺ©μ΄ 킀에 따라 μ‚¬μ „μˆœμœΌλ‘œ μ •λ ¬λ˜μ–΄ μžˆλ‹€.

단점

  • μ‘°νšŒλŠ” ν•΄μ‹œ ν…Œμ΄λΈ”λ³΄λ‹€ 느릴 수 μžˆλ‹€.

    • 특히 μ£Ό λ©”λͺ¨λ¦¬μ— λΉ„ν•΄ μž„μ˜ μ ‘κ·Ό λΉ„μš©μ΄ 큰 ν•˜λ“œ λ””μŠ€ν¬ λ“œλΌμ΄λΈŒμ™€ 같은 보쑰 κΈ°μ–΅μž₯μΉ˜μ—μ„œ 직접 μ½λŠ”λ‹€λ©΄ λ”μš± κ·Έλ ‡λ‹€.
  • λΆ€λ™μ†Œμˆ˜μ κ³Ό 같이 λ¬Έμžμ—΄λ‘œ μž₯ν™©ν•˜κ²Œ ν‘œμ‹œλ˜λŠ” 자료의 경우 λ¬΄μ˜λ―Έν•˜κ²Œ 길게 λŠ˜μ–΄μ§„ 접두사와 λ…Έλ“œλ₯Ό κ°€μ§ˆ 수 μžˆλ‹€.
  • νŠΈλΌμ΄κ°€ λ©”λͺ¨λ¦¬λ₯Ό 더 μ†ŒλΉ„ν•  수 μžˆλ‹€.

    • λŒ€λΆ€λΆ„μ˜ ν•΄μ‹œ ν…Œμ΄λΈ”μ—μ„œλŠ” 전체 ν•­λͺ©μ„ ν•˜λ‚˜μ˜ λ©”λͺ¨λ¦¬ 청크에 올리곀 ν•˜μ§€λ§Œ, νŠΈλΌμ΄μ—μ„œλŠ” 검색 λ¬Έμžμ—΄μ˜ 각 λ¬Έμžλ§ˆλ‹€ λ©”λͺ¨λ¦¬κ°€ 할당될 수 μžˆλ‹€.

πŸͺš κ΅¬ν˜„

트리 ꡬ쑰의 각 λ…Έλ“œμ—λŠ” 각 λ¬Έμžμ—΄μ˜ 일뢀λ₯Ό ν¬ν•¨ν•˜λ©°, μžμ‹ κ³Ό μ—°κ²°λ˜λŠ” λ¬Έμžμ—΄μ˜ 일뢀λ₯Ό κ°€μ§€κ³  μžˆμ–΄μ•Ό ν•œλ‹€λŠ” 점을 λͺ…심!

μƒμ„±μž/클래슀 μ •μ˜

  • 루트 λ…Έλ“œλŠ” μ•„λ¬΄λŸ° λ¬Έμžμ—΄λ„ ν¬ν•¨ν•˜μ§€ μ•Šκ³  λͺ¨λ“  λ¬Έμžμ—΄μ˜ 접두사듀을 μžμ‹ λ°°μ—΄λ‘œ κ°–κ³  μžˆμ–΄μ•Ό ν•œλ‹€.
  • Node ν΄λž˜μŠ€λŠ” 각 Node 의 정보λ₯Ό μ •μ˜ν•œ 클래슀둜, μžμ‹ μ˜ 문자, μ—°κ²°λ˜λŠ” λ¬Έμžλ“€μ˜ 정보λ₯Ό κ°–κ³  있고 λ¬Έμžμ—΄μ΄ μ™„μ„±λ˜λŠ”κ°€ μ—¬λΆ€ λ˜ν•œ μ €μž₯ν•˜κ³  μžˆλ‹€.
class Trie { Node root; static final int ALPHABET_SIZE = 26; // μ•ŒνŒŒλ²³ 개수: 26 public Trie() { this.root = new Node(); this.root.val = ' '; } public static class Node { Node[] child = new Node[ALPHABET_SIZE]; // λ’€λ‘œ μ—°κ²°λ˜λŠ” λ¬Έμžμ—΄μ„ indexν™”ν•˜μ—¬ μ €μž₯ν•˜λŠ” λ°°μ—΄ boolean isTerminal = false; // ν˜„μž¬ λ…Έλ“œκ°€ λ¬Έμžμ—΄μ˜ λ§ˆμ§€λ§‰μΈμ§€ μ—¬λΆ€ int childNum = 0; // ν˜„μž¬ λ…Έλ“œμ— μ—°κ²°λœ λ¬Έμžμ—΄ 개수 char val; // ν˜„μž¬ λ…Έλ“œμ˜ κ°’ } }

λ¬Έμžμ—΄ μ‚½μž…(insert, charToInt)

  • charToInt() λ©”μ†Œλ“œλŠ” 각 λ¬Έμžμ—΄μ˜ 1개 단어λ₯Ό int ν˜• 숫자둜 λ³€ν™˜ν•΄μ£ΌλŠ” λ©”μ†Œλ“œλ‹€.
  • insert() λ©”μ†Œλ“œλŠ” 전체 λ¬Έμžμ—΄μ„ μͺΌκ°œμ„œ 각 λ…Έλ“œ(Node)에 μ €μž₯ν•˜λŠ” λ©”μ†Œλ“œλ‹€.
private int charToInt(char c) { return c - 'a'; // μ†Œλ¬Έμžλ§Œ μ·¨κΈ‰ν•œλ‹€λŠ” κ°€μ •ν•˜μ— `a`λ₯Ό λΊ€λ‹€. } public void insert(String str) { int len = str.length(); Node cur = this.root; for (int i = 0; i < len; i++) { char c = str.charAt(i); int num = this.charToInt(c); if (cur.child[num] == null) { // 기쑴에 null이면 μ—°κ²° λ¬Έμžμ—΄λ‘œ 처음 μΆ”κ°€λ˜λŠ” 것 cur.child[num] = new Node(); cur.child[num].val = c; cur.childNum++; } cur = cur.child[num]; } cur.isTerminal = true; }

μ°ΎκΈ°(find)

  • 단어λ₯Ό μ €μž₯ν–ˆμœΌλ©΄ μ €μž₯λ˜μ–΄ μžˆλŠ”μ§€ 확인할 수 μžˆμ–΄μ•Ό ν•œλ‹€.
public boolean find(String str) { int len = str.length(); Node cur = this.root; for (int i = 0; i < len; i++) { char c = str.charAt(i); int num = this.charToInt(c); if (cur.child[num] == null) return false; cur = cur.child[num]; } return cur != null && cur.isTerminal; }

전체 μ €μž₯된 λ¬Έμžμ—΄ λ‚΄μ—­ 좜λ ₯

  • λͺ¨λ“  μ €μž₯된 λ‹¨μ–΄μ˜ 내역을 μ•ŒκΈ° μ‰½κ²Œ 좜λ ₯ν•  수 μžˆλ„λ‘ ν•˜λŠ” λ©”μ†Œλ“œλ₯Ό κ΅¬ν˜„ν•΄λ³Ό 수 μžˆλ‹€.
private char intToChar(int i) { return (char) (i + (int) 'a'); } // μ‚¬μš©μžκ°€ κ°„νŽΈνžˆ 호좜만 ν•˜λ©΄ λ˜λŠ” ν•¨μˆ˜ public void printTrie() { this.printTrie(this.root, 0, new StringBuilder()); } // λ‚΄λΆ€μ—μ„œ μž¬κ·€μ μœΌλ‘œ μˆœν™˜ν•˜μ—¬ λ…Έλ“œμ— μ €μž₯된 κ°’λ“€ μΆ”μΆœν•΄ 좜λ ₯ private void printTrie(Node node, int idx, StringBuilder sb) { Node cur = node; Node[] child = cur.child; StringBuilder builder = new StringBuilder(sb); // 루트 λ…Έλ“œμ—λŠ” μ €μž₯된 것이 μ—†μœΌλ―€λ‘œ κ·Έ μ™Έμ˜ κ²½μš°μ—λ§Œ append if (!cur.equals(this.root)) builder.append(intToChar(idx)); // μ™„μ„± λ…Έλ“œλΌλ©΄ 좜λ ₯ if (cur.isTerminal) System.out.println(builder); // μ—°κ²°λœ λ…Έλ“œλ“€μ„ μˆœν™˜ν•˜κΈ° μœ„ν•΄ 반볡문 μ‚¬μš© for (int i = 0; i < ALPHABET_SIZE; i++) { // null이라면 μ €μž₯된 것이 μ—†μœΌλ―€λ‘œ 패슀 if (cur.child[i] == null) continue; printTrie(child[i], i, builder); } }

μ‚­μ œ

  • μ‚­μ œλŠ” μž¬κ·€μ μœΌλ‘œ bottom-up λ°©μ‹μœΌλ‘œ μ§„ν–‰λ˜κ³ , 3κ°€μ§€ κ²½μš°κ°€ μžˆλ‹€.
  • μ‚­μ œν•  λ¬Έμžκ°€ λ‹€λ₯Έ 문자의 접두사인 경우 - isTerminal 을 false λ³€κ²½

    1. Do λŠ” Door 의 접두사가 λœλ‹€. λ”°λΌμ„œ, Do λ₯Ό μ‚­μ œν•œλ‹€λ©΄ D , o μ—μ„œ o 에 isTerminal 만 false 둜 λ³€κ²½ν•œλ‹€.
    2. λ‹¨μˆœνžˆ μ‚­μ œν•˜λ©΄ Door λ˜ν•œ μ‚¬λΌμ§€κ²Œ λœλ‹€.
  • μ‚­μ œν•  λ¬Έμžκ°€ κ³ μœ ν•˜μ—¬ λ‹€λ₯Έ λ¬Έμžμ™€ 연관이 μ—†λŠ” 경우 - κ΄€λ ¨ λͺ¨λ“  λ…Έλ“œ μ‚­μ œ
  • μ‚­μ œν•  문자의 일뢀가 전체 μ‚­μ œ 문자의 접두사인 경우 - λ‹€λ₯Έ λ¬Έμžμ— μ˜ν•­κ°€μ§€ μ•ŠλŠ” κ³³κΉŒμ§€λ§Œ μ‚­μ œ

    1. Door λ₯Ό μ‚­μ œν•˜λ €κ³  ν•œλ‹€λ©΄ Do κ°€ μžˆκΈ°μ—, 전체 μ‚­μ œλ₯Ό ν•  수 μ—†κ³  Door μ—μ„œ λ’€μ˜ o , r 만 μ‚­μ œν•œλ‹€.
public void delete(String str) { delete(this.root, str, 0); } private void delete(Node cur, String str, int idx) { int len = str.length(); if ((cur.childNum == 0 && idx != len) || (idx == len && !cur.isTerminal)) { throw new NoSuchElementException("Value" + str + " does not exist in Trie!"); } if (idx == len) { cur.isTerminal = false; if (cur.childNum == 0) cur = null; else { char c = str.charAt(idx); int num = charToInt(c); delete(cur.child[num], str, idx + 1); if (cur.child[num] == null) cur.childNum--; if (cur.childNum == 0 && !cur.isTerminal) cur = null; } } }

μ‹€μ œλ‘œλŠ” HashMap 을 μ‚¬μš©ν•΄ κ΅¬ν˜„ν•˜λŠ” 것이 더 νš¨μœ¨μ μ΄λ‹€. μ•„λž˜λŠ” 이λ₯Ό μ‚¬μš©ν•œ κ΅¬ν˜„μ΄λ‹€.

클래슀 생성

  • TrieNode λŠ”Β μžμ‹λ…Έλ“œ λ§΅κ³ΌΒ isLastChar λ₯Ό κ°€μ§€κ³  μžˆλ‹€.
  • isLastChar λŠ” 'DEV'λΌλŠ” λ‹¨μ–΄μ—μ„œ [D], [E]λŠ” λ§ˆμ§€λ§‰ κΈ€μžκ°€ μ•„λ‹ˆμ§€λ§Œ [V]λŠ” λ§ˆμ§€λ§‰ κΈ€μžλ‘œ, ν•œ 단어가 μ™„μ„±λ˜λŠ” μ‹œμ μž„μ„ μ•Œ 수 μžˆλ„λ‘ ν•˜λŠ” 값이닀.
public class TrieNode { private Map<Character, TrieNode> childNodes = new HashMap<>(); // λ§ˆμ§€λ§‰ κΈ€μž μ—¬λΆ€ private boolean isLastChar; // μžμ‹ λ…Έλ“œ λ§΅ Getter Map<Character, TrieNode> getChildNodes() { return this.childNodes; } // λ§ˆμ§€λ§‰ κΈ€μžμΈμ§€ μ—¬λΆ€ Getter boolean isLastChar() { return this.isLastChar; } // λ§ˆμ§€λ§‰ κΈ€μžμΈμ§€ μ—¬λΆ€ Setter void setIsLastChar(boolean isLastChar) { this.isLastChar = isLastChar; } }
  • TrieλŠ” 기본적으둜 빈 λ¬Έμžμ—΄μ„ κ°€μ§€λŠ” 루트 λ…Έλ“œλ§Œ κ°€μ§€κ³  μžˆλ‹€.
  • 이 후에 λ‚˜μ˜¬ insert() λ₯Ό 톡해 단어λ₯Ό λ„£μ–΄ 그에 맞게 μžμ‹ λ…Έλ“œκ°€ μƒμ„±λœλ‹€.
public class Trie { private TrieNode rootNode; public Trie() { rootNode = new TrieNode(); } }

insert

  • μž…λ ₯받은 λ‹¨μ–΄μ˜ 각 μ•ŒνŒŒλ²³μ„ κ³„μΈ΅κ΅¬μ‘°μ˜ μžμ‹ λ…Έλ“œλ‘œ λ§Œλ“€μ–΄ λ„£λŠ”λ‹€.

    • 이미 같은 μ•ŒνŒŒλ²³μ΄ μ‘΄μž¬ν•˜λ©΄ 곡톡 μ ‘λ‘μ–΄κΉŒμ§€λŠ” μƒμ„±ν•˜μ§€ μ•ŠλŠ”λ‹€.
  • 즉, ν•΄λ‹Ή 계측 문자의 μžμ‹ λ…Έλ“œκ°€ μ‘΄μž¬ν•˜μ§€ μ•Šμ„ λ•Œλ§Œ μžμ‹ λ…Έλ“œλ₯Ό 생성해쀀닀.
  • 이후 λ§ˆμ§€λ§‰ κΈ€μžμ—λŠ” "μ—¬κΈ°κΉŒμ§€λ₯Ό 끝으둜 ν•˜λŠ” 단어가 μ‘΄μž¬ν•œλ‹€"λŠ” ν‘œμ‹œλ₯Ό μœ„ν•΄ isLastChar λ₯Ό true 둜 ν•΄μ€€λ‹€.
void insert(String word) { TrieNode thisNode = this.rootNode; for (int i = 0; i < word.length(); i++) { thisNode = thisNode.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode()); } thisNode.setIsLastChar(true); }

contains

  • νŠΉμ • 단어가 Trie에 μ‘΄μž¬ν•˜λŠ”μ§€λ₯Ό ν™•μΈν•˜κΈ° μœ„ν•΄μ„œλŠ” μ•„λž˜ 2κ°€μ§€ 쑰건을 λ§Œμ‘±ν•΄μ•Ό ν•œλ‹€.

    • 루트 λ…Έλ“œλΆ€ν„° μˆœμ„œλŒ€λ‘œ μ•ŒνŒŒλ²³μ΄ μΌμΉ˜ν•˜λŠ” μžμ‹ λ…Έλ“œλ“€μ΄ μ‘΄μž¬ν•  것
    • ν•΄λ‹Ή λ‹¨μ–΄μ˜ λ§ˆμ§€λ§‰ κΈ€μžμ— ν•΄λ‹Ήν•˜λŠ” λ…Έλ“œμ˜ isLastChar κ°€ true 일 것
boolean contains(String word) { TrieNode thisNode = this.rootNode; for (int i = 0; i < word.length(); i++) { char character = word.charAt(i); TrieNode node = thisNode.getChildNodes().get(character); if (node == null) return false; thisNode = node; } return thisNode.isLastChar(); }

delete

  • Trie에 λ„£μ—ˆλ˜ 단어λ₯Ό μ‚­μ œν•˜λŠ” 과정이닀.
  • contains() 처럼 μ£Όμ–΄μ§„ 단어λ₯Ό μ°Ύμ•„ ν•˜μœ„ λ…Έλ“œλ‘œ 단어 길이만큼 λ‚΄λ €κ°„λ‹€.
  • 단, λ…Έλ“œλ“€μ΄ λΆ€λͺ¨ λ…Έλ“œμ˜ 정보λ₯Ό κ°€μ§€κ³  μžˆμ§€ μ•ŠκΈ°μ—, ν•˜μœ„ λ…Έλ“œλ‘œ λ‚΄λ €κ°€λ©° μ‚­μ œ λŒ€μƒ 단어λ₯Ό νƒμƒ‰ν•˜κ³  λ‹€μ‹œ μ˜¬λΌμ˜€λ©΄μ„œ μ‚­μ œν•˜λŠ” 과정이 μ½œλ°±ν˜•μ‹μœΌλ‘œ κ΅¬ν˜„λ˜μ–΄μ•Ό ν•œλ‹€λŠ” 것이닀.

그리고 μ•„λž˜μ˜ μ‚­μ œ 쑰건듀을 확인해야 ν•œλ‹€.

  1. μžμ‹ λ…Έλ“œλ₯Ό κ°€μ§€κ³  μžˆμ§€ μ•Šμ•„μ•Ό ν•œλ‹€.
  2. μ‚­μ œλ₯Ό μ‹œμž‘ν•˜λŠ” 첫 λ…Έλ“œλŠ” isLastChar == true μ—¬μ•Ό ν•œλ‹€.
  3. μ‚­μ œλ₯Ό μ§„ν–‰ν•˜λŠ” μ€‘μ—λŠ” isLastChar == false μ—¬μ•Ό ν•œλ‹€.
void delete(String word) { delete(this.rootNode, word, 0); } private void delete(TrieNode thisNode, String word, int index) { char character = word.charAt(index); // Trie에 μ—†λŠ” 단어인 경우 μ—λŸ¬ 좜λ ₯ if(!thisNode.getChildNodes().containsKey(character)) throw new Error("There is no [" + word + "] in this Trie."); TrieNode childNode = thisNode.getChildNodes().get(character); index++; // λ‹¨μ–΄μ˜ 길이만큼 ν•˜μœ„ λ…Έλ“œλ‘œ μž¬κ·€ if(index == word.length()) { // μ‚­μ œμ‘°κ±΄ 2번 ν•­λͺ© // PO와 같이 λ…Έλ“œλŠ” μ‘΄μž¬ν•˜μ§€λ§Œ insertν•œ 단어가 μ•„λ‹Œ 경우 μ—λŸ¬ 좜λ ₯ if (!childNode.isLastChar()) throw new Error("There is no [" + word + "] in this Trie."); childNode.setIsLastChar(false); // μ‚­μ œμ‘°κ±΄ 1번 ν•­λͺ© // μ‚­μ œ λŒ€μƒ λ‹¨μ–΄μ˜ 제일 끝으둜써 μžμ‹ λ…Έλ“œκ°€ μ—†μœΌλ©΄(이 단어λ₯Ό ν¬ν•¨ν•˜λŠ” 더 κΈ΄ 단어가 μ—†μœΌλ©΄) μ‚­μ œ μ‹œμž‘ if (childNode.getChildNodes().isEmpty()) thisNode.getChildNodes().remove(character); } else { delete(childNode, word, index); // μ½œλ°±ν•¨μˆ˜λΆ€λΆ„ // μ‚­μ œμ‘°κ±΄ 1,3번 ν•­λͺ© // μ‚­μ œ 쀑, μžμ‹ λ…Έλ“œκ°€ μ—†κ³  ν˜„μž¬ λ…Έλ“œλ‘œ λλ‚˜λŠ” λ‹€λ₯Έ 단어가 μ—†λŠ” 경우 이 λ…Έλ“œ μ‚­μ œ if(!childNode.isLastChar() && childNode.getChildNodes().isEmpty()) thisNode.getChildNodes().remove(character); } }

πŸ“• μ°Έκ³ 

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€